#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 4e4 + 5;
const int MOD = 999911659;
ll n, g;
vector<ll> a;
vector<ll> b{2, 3, 4679, 35617};
vector<ll> k;
ll f[N], inv[N];
ll fastpow(ll b, ll p, ll mod) {
  ll res = 1;
  while (p) {
    if (p & 1) res = res * b % mod;
    b = b * b % mod;
    p >>= 1;
  }
  return res;
}
void init(ll p) {
  f[0] = 1;
  rep(i, 1, p - 1) f[i] = i * f[i - 1] % p;
}
ll C(ll n, ll m, ll p) {
  if (n < m) return 0;
  return f[n] * fastpow(f[m], p - 2, p) % p * fastpow(f[n - m], p - 2, p) % p;
}
ll lucas(int n, int m, int p) {
  if (n < m) return 0;
  if (m == 0) return 1;
  return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
ll crt() {
  ll all = MOD - 1;
  ll res = 0;
  rep(i, 0, 3) {
    ll x = all / b[i];
    ll y = fastpow(x, b[i] - 2, b[i]);
    res = (res + (a[i] * (x * y % all)) % all) % all;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> g;
  if (g % MOD == 0) {
    cout << 0;
    return 0;
  }
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      k.push_back(i);
      ll j = n / i;
      if (j != i) k.push_back(j);
    }
  }
  for (ll p : b) {
    init(p);
    ll r = 0;
    for (ll x : k) {
      ll y = lucas(n, x, p);
      r = (r + y) % p;
    }
    a.push_back(r);
  }
  ll p = crt();
  ll ans = fastpow(g, p, MOD);
  cout << ans;
  return 0;
}